import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Stack;

public class Solution895 {

    Map<Integer,Integer> map=new HashMap<>();
    Map<Integer, Stack<Integer>> map2=new HashMap<>();
    PriorityQueue<int[]> priorityQueue=new PriorityQueue<>((a,b)->a[1]==b[1]?b[2]-a[2]:b[1]-a[1]);
    int c=0;

    public Solution895() {

    }

    public void push(int val) {
        map.put(val,map.getOrDefault(val,0)+1);
        if (!map2.containsKey(val)){
            map2.put(val,new Stack<>());
            map2.get(val).push(-1);
        }
        map2.get(val).push(c);
        c++;
        priorityQueue.offer(new int[]{val,map.get(val),map2.get(val).peek()});
    }

    public int pop() {
        while (priorityQueue.peek()[1]!=map.get(priorityQueue.peek()[0]) || priorityQueue.peek()[2]!=map2.get(priorityQueue.peek()[0]).peek()){
            priorityQueue.poll();
        }
        int ans=priorityQueue.peek()[0];
        map.put(ans,map.get(ans)-1);
        map2.get(ans).pop();
        priorityQueue.offer(new int[]{ans,map.get(ans),map2.get(ans).peek()});
        return ans;
    }

    public static void main(String[] args) {
        Solution895 solution895=new Solution895();
        solution895.push(5);
        solution895.push(7);
        solution895.push(5);
        solution895.push(7);
        solution895.push(4);
        solution895.push(5);
        System.out.println(solution895.pop());
        System.out.println(solution895.pop());
        System.out.println(solution895.pop());
        System.out.println(solution895.pop());
    }
}
